import java.util.Arrays;

/**
 * @author sk.z
 * 2023/5/6
 * 43. 字符串相乘
 * 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
 * 注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
 **/
public class Solution {

    private static int PLACE_VALUE = 10000;
    private static int PLACE_LENGTH = 4;

    public static void main(String[] args) {
        String multiply = multiply("6994",
                "36");
        System.out.println(multiply);
    }

    public static String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        int[] arr1 = strToNum(num1);
        int[] arr2 = strToNum(num2);
        int[] mul = mul(arr1, arr2);
        /*
        BigInteger bi = new BigInteger(num1);
        BigInteger b2 = new BigInteger(num2);
        System.out.println(bi.multiply(b2));
         */
        return numToStr(mul);
    }

    private static int[] mul(int[] num1, int[] num2) {
        int[] result = new int[num1.length + num2.length + 1];
        int xSize = num1.length;
        int ySize = num2.length;
        for (int x = xSize - 1; x >= 0; x--) {
            for (int y = ySize - 1; y >= 0; y--) {
                int index = x + y + 2;
                intoResult(result, index, num1[x] * num2[y]);
            }
        }
        return result;
    }

    private static void intoResult(int[] result, int index, int value) {
        int sum = result[index] + value;
        int upValue = sum / PLACE_VALUE;
        if (upValue == 0) {
            result[index] = sum;
        } else {
            result[index] = sum % PLACE_VALUE;
            intoResult(result, index - 1, upValue);
        }
    }

    private static int[] strToNum(String s) {
        char[] chars = s.toCharArray();
        int size = (chars.length / PLACE_LENGTH);
        if ((size * PLACE_LENGTH) < chars.length) {
            size++;
        }
        int[] num = new int[size];
        int i = size - 1;
        int end = chars.length;
        int start = end - PLACE_LENGTH;
        while (start < chars.length) {
            if (start >= 0) {
                String place = new String(Arrays.copyOfRange(chars, start, end));
                num[i] = Integer.parseInt(place);
                if (start == 0) {
                    break;
                }
            } else {
                String place = new String(Arrays.copyOfRange(chars, 0, end));
                num[i] = Integer.parseInt(place);
                break;
            }
            i--;
            end = start;
            start = end - PLACE_LENGTH;
        }
        return num;
    }

    private static String numToStr(int[] num) {
        StringBuilder sb = new StringBuilder();
        for (int i : num) {
            String s = Integer.toString(i);
            for (int j = 0; j < PLACE_LENGTH - s.length(); j++) {
                sb.append("0");
            }
            sb.append(i);
        }
        while (sb.charAt(0) == '0') {
            sb.deleteCharAt(0);
        }
        return sb.toString();
    }

}
